package sortedcollection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import be.kuleuven.cs.som.annotate.Basic;

/**
 * An collection that is always been sorted by the natural ordering of the given element.
 * 
 * @invar The elements will be sorted ascending all the time (the biggest at the end).
 * 		| hasProperElements()
 * 
 * @author Molderez Tom, 2de bach Ingenieurswetenschappen Computerwetenschappen-Elektrotechniek and Reniers Jorn, 2de bach Ingenieurswetenschappen Werktuigkunde-Computerwetenschappen
 * @version 2.0
 *
 * @param <E> A class implementing the Comparable interface.
 */
public class SortedCollection<E extends Comparable<? super E>> implements Collection<E> {
	
	private final List<E> list = new ArrayList<E>();
	
	/**
	 * Creates a new ArrayListSort.
	 * 
	 * @post The sortedCollection will not contain any element.
	 * 		| (new this).isEmpty() == true
	 */
	public SortedCollection() {
	}
	
	/**
	 * Checks if this list is ordered ascending (the biggest at the end).
	 * 
	 * @return True if the list contains no objects at all.	
	 * 		| if this.isEmpty()
	 * 		|	result == true
	 * @return True when the list is ordered ascending, otherwise false.
	 * 		| let ordered = true
	 * 		| for each index in {1,2,..,this.size()-1}
	 * 		|	if this.get(index - 1).compareTo(this.get(index)) > 0
	 * 		|	  then ordered = false
	 * 		| result == ordered 
	 */
	public boolean hasProperElements() {
		for(int index = 1; index < this.size(); index ++)
			if(list.get(index - 1).compareTo(list.get(index)) > 0)
				return false;
		return true;
	}
	
	/**
	 * Adds an element to the SortedCollection at the position to respect the sort definition.
	 * 
	 * The time complexity for adding an element is log(n). The position is calculated
	 * using binary search.
	 * 
	 * @param element The element to be added.
	 * @post The element will be added to the list.
	 * 		| (this new).contains(element)
	 */
	@Override
	public boolean add(E element) {
		if(this.isEmpty())
			list.add(element);
		else {
			int index = Collections.binarySearch(list, element); 
			if(index < 0) 
				index = - index -1;
			list.add(index, element);
		}
		return true;
	}
	
	/**
	 * This method adds all the elements in the given collection to this. The complexity is m*log(m)*n,
	 * with n the amount of elements to add, m the total amounts in the sortedCollection after adding.
	 * @param collection A collection with elements of the same class as this.
	 * @post This will contain all the elements of the collection.
	 * 		| for each element in {collection}
	 * 		|	(this new).contains(element)
	 * 
	 */
	@Override
	public boolean addAll(Collection<? extends E> collection) throws NullPointerException {
		list.addAll(collection);
		Collections.sort(list);
		return true;
	}

	/**
	 * Returns the element for which index elements are less according the comparable interface. 
	 * 
	 * @throws IndexOutOfBoundsException
	 * 		When the index is not legal.
	 * 		| index < 0 || index >= this.size()
	 */
	@Basic
	public E get(int index) throws IndexOutOfBoundsException {
		return list.get(index);
	}
	
	@Override
	public Iterator<E> iterator() {
		return list.iterator();
	}

	@Override
	public int size() {
		return list.size();
	}

	@Override
	public void clear() {
		list.clear();
	}

	@Override
	public boolean contains(Object o) throws ClassCastException, NullPointerException {
		return list.contains(o);
	}

	@Override
	public boolean containsAll(Collection<?> c) throws ClassCastException, NullPointerException {
		return list.containsAll(c);
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	@Override
	public boolean remove(Object o) {
		return list.remove(o);
	}

	@Override
	public boolean removeAll(Collection<?> c) throws ClassCastException, NullPointerException {
		return list.removeAll(c);
	}

	@Override
	public boolean retainAll(Collection<?> c) throws ClassCastException, NullPointerException {
		return list.retainAll(c);
	}

	@Override
	public Object[] toArray() {
		return list.toArray();
	}

	@Override
	public <E> E[] toArray(E[] a) throws NullPointerException, ArrayStoreException {
		return list.toArray(a);
	}

}
